[% setvar title Backtracking %]
<div id="archive-notice">
    <h3>This file is part of the Perl 6 Archive</h3>
    <p>To see what is currently happening visit <a href="http://www.perl6.org/">http://www.perl6.org/</a></p>
</div>
<div class='pod'>
<a name='TITLE'></a><h1>TITLE</h1>
<p>Backtracking</p>
<a name='VERSION'></a><h1>VERSION</h1>
<pre>  Maintainer: iVAN Georgiev &lt;<a href='mailto:raptor@unacs.bg'>raptor@unacs.bg</a>&gt;
  Date: 14 Aug 2000
  Mailing List: <a href='mailto:perl6-language@perl.org'>perl6-language@perl.org</a>
  Number: 104
  Version: 1
  Status: Developing</pre>
<a name='ABSTRACT'></a><h1>ABSTRACT</h1>
<p>Backtraking mechanism is core functionality of languages like PROLOG.
Perl-regex engine has this ability too.</p>
<p>Adding this mechanism to our programming arsenal will bring alot of
new functionality. Will help us solve problems that otherwise cost us
alot of time and effort (laziness).</p>
<p>A new paradigm to Perl - DECLARATIVE programming.</p>
<a name='DESCRIPTION'></a><h1>DESCRIPTION</h1>
<p>The whole gang-bang can be done with only two new operators: andthen, orthen.</p>
<p>They behave similarly like &amp;&amp;, ||, and, or operator with one main
distinction they &quot;backtrack&quot; for example:</p>
<p>{ block1 } <b>andthen</b> { block2 };</p>
<p>mean this:</p>
<pre> if &quot;block1&quot; return true(1) &quot;block2&quot; is evaluated then 
     if &quot;block2&quot; return true(1) the end result is true(1)
     if &quot;block2&quot; return false(0) 
         we evaluate &quot;block1&quot; again i.e start from the beginning.
 but if &quot;block1&quot; return false(0) the end result is false(0)
 </pre>
<p>or to be more clear this is the Perl equivalent/example:</p>
<pre> my $res = 0;
 {
  my $ex1;
  { $l = (rand() &gt; 0.3) ? 1:0;print &quot;block1=$l\n&quot;; $ex1=$l};
  if ($ex1)
   {
    my $ex2;
    { $r = (rand() &gt; 0.7) ? 1:0;print &quot;block2=$r\n&quot;; $ex2=$r};
     if ($ex2) { $res = 1 } else { redo }
   };
  };

 print &quot;The result is : $res\n&quot;;</pre>
<p>Similarly &quot;orthen&quot;:</p>
<pre> { block1 } B&lt;orthen&gt; { block2 };</pre>
<p>mean this:</p>
<pre> if &quot;block1&quot; return true(1) the end result is true(1)
 but if &quot;block1&quot; return false(0) &quot;block2&quot; is evaluated then 
     if &quot;block2&quot; return true(1) the end result is true(1)
     if &quot;block2&quot; return false(0) 
 we evaluate &quot;block1&quot; again i.e start from the beginning.</pre>
<p>OR this:</p>
<pre> if &quot;block1&quot; return true(1) 
     we evaluate &quot;block2&quot; and return true(1)
     w/o taking in consideration the result of &quot;block2&quot; evaluation.
 but if &quot;block1&quot; return false(0) &quot;block2&quot; is evaluated then 
     if &quot;block2&quot; return true(1) the end result is true(1)
     if &quot;block2&quot; return false(0) 
 we evaluate &quot;block1&quot; again i.e start from the beginning.</pre>
<a name='USAGE'></a><h2>USAGE</h2>
<p>Good candidates for &quot;backtracking&quot; are XML processors,
analytical &quot;permutations!&quot;, expert systems and many more...</p>
<p>Cycle:</p>
<pre> my $i = 0;
 {$i++; $i &lt;= 10 } andthen {print $i};</pre>
<p>equivalent to:</p>
<pre> for (my $i=1;$i++;$i&lt;=10) {print $i};</pre>
<a name='FURTHER WORK'></a><h2>FURTHER WORK</h2>
<p>As you saw I tried to propose as small change to the perl
core/language as possible, which can be easily implemented.
What else we can expect?</p>
<p>One good addition that can we thought about is implementing
the Perl BLOCK's as forth-state BLACKBOX structure not as
it is now i.e. two states, what I mean ?</p>
<p>Currently AFAIK we have &quot;entering&quot; and &quot;leaving&quot; the block.
We can have &quot;direction&quot; i.e. with &quot;backtrack&quot; mechanism we
can enter the block from previous block or from the next one -
the four &quot;states&quot; are - enter(-&gt;),leave(-&gt;),reevaluate(&lt;-),fall(&lt;-),
we will need also to count how many times the block has been
in all of these states. We can leave the old behaviour as
default(in the name of speed) and only when the Perl programmer
need these states to use &quot;state&quot; pragma.</p>
<pre>   use state &quot;2&quot;;
   use state &quot;4&quot;;
 </pre>
<p>BUT this will be alot of work, so for now andthen, orthen
are enough. If backtracking is made as more general algorithm
it can be used both by Perl itself and regex engine ?!!</p>
<a name='IMPLEMENTATION'></a><h1>IMPLEMENTATION</h1>
<p>There is many possible implementations one of them you saw
in DESCRIPTION section, it can also be implemented as
while, until cycle...</p>
<p>If I was perl-core hacker you now will be reading
and applying the patch :&quot;), I believe that this can be very
easily implemented as just adding several lines in perly.y
(please excuse my ignorance if this is not the case)....</p>
<a name='REFERENCES'></a><h1>REFERENCES</h1>
<p>perldoc perlre</p>
<p>The Prolog Language:
<a href='http://www.sics.se/SICS-reports/SICS-T--93-01--SE/report_10.html' target='_blank'>www.sics.se</a></p>
<p>Coroutining facilities:
<a href='http://www.sics.se/SICS-reports/SICS-T--93-01--SE/report_8.html' target='_blank'>www.sics.se</a></p>
</div>
